// https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/

// 算法思路总结：
// 1. 动态规划统计最长递增子序列的个数
// 2. len[i]记录以nums[i]结尾的LIS长度
// 3. count[i]记录对应长度的序列个数
// 4. 时间复杂度：O(n²)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int findNumberOfLIS(vector<int>& nums) 
    {
        int m = nums.size();
        if (m == 1) return 1;

        vector<int> len(m, 1), count(m, 1);
        for (int i = 1 ; i < m ; i++)
        {
            for (int j = 0 ; j < i ; j++)
            {
                if (nums[j] < nums[i])
                {
                    if (len[j] + 1 == len[i])
                    {
                        count[i] += count[j];
                    }
                    else if (len[j] + 1 > len[i])
                    {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }
        }

        int retc = 0, retl = 0;
        for (int i = 0 ; i < m ; i++)
        {
            if (retl < len[i])
            {
                retl = len[i];
                retc = count[i];
            }
            else if (retl == len[i])
            {
                retc += count[i];
            }
        }

        return retc;
    }
};

int main()
{
    vector<int> v1 = {1,3,5,4,7}, v2 = {2,2,2,2,2};
    Solution sol;

    cout << sol.findNumberOfLIS(v1) << endl;
    cout << sol.findNumberOfLIS(v2) << endl;

    return 0;
}